package leetcode101_xqzhao

// TODO 【没思路】 单词拆分 【-】 动态规划 + 哈希表 [困难]

func wordBreak(s string, wordDict []string) bool {
	n := len(wordDict)
	m := make(map[string]bool, n)
	for _, v := range wordDict {
		m[v] = true
	}
	m[""] = true

	// 定义 dp 数组
	dp := make([]bool, len(s)+1)
	// 设置初始值
	dp[0] = true // 作用, 当 j=0 的时候, 判断 s[0:i] 是否是可拆分的单词
	// 状态转移
	for i := 1; i <= len(s); i++ {
		for j := i - 1; j >= 0; j-- {
			str := s[j:i]
			if m[str] && dp[j] {
				dp[i] = true
			}
		}
	}
	return dp[len(s)]
}
